/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Algorithm;

import GameLogic.Tower;
import java.util.List;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 *
 * @author Ix
 */
public class KDTree {
    final int LEAF_TRESHOLD = 2;
    private class node
    {
        int axis;
        int val;
        Tower t;
        node parent,
             childA,
             childB;
        ArrayList<Tower> leafNodes;
    }
    
    node parent;
    
    public int cmp(int a1, int b1, int a2, int b2) {
        if(a1 > b1)
            return 1;
        if(a1 < b1)
            return -1;
        if(a2 > b2)
            return 1;
        if(a2 < b2)
            return -1;
        return 0;
        
    }
    Comparator<Tower> cx = new Comparator<Tower>() {
            public int compare(Tower a, Tower b) {
                return cmp(a.x * 2 + a.type.size, b.x * 2 + b.type.size, 
                           a.y * 2 + a.type.size, b.y * 2 + b.type.size);
            }},
                      cy = new Comparator<Tower>() {
            public int compare(Tower a, Tower b) {
                return cmp(a.y * 2 + a.type.size, b.y * 2 + b.type.size, 
                           a.x * 2 + a.type.size, b.x * 2 + b.type.size);
            }
        };
    
    private void SortArray(Tower[] t, int a)
    {
        //sort along corresponding axis
        if(a == 0)
            Arrays.sort(t, cx);
        else
            Arrays.sort(t, cy);
    }
    
    public ArrayList<Tower> GetNearbyTowers(Point2D p, double dist)
    {
        if(parent == null)
            return null;
        return nearbySub(p, dist, parent);
    }
    
    private ArrayList<Tower> nearbySub(Point2D p, double dist, node n)
    {
        ArrayList<Tower> ret = new ArrayList<Tower>();
        Tower t;
        double d, d2 = dist*dist;
        if(n.leafNodes != null)
        {
            for(int i = 0; i < n.leafNodes.size(); i++)
            {
                t = n.leafNodes.get(i);
                d = Pathfinding.GetDist2(p, t.getPosition());
                if(d <= d2)
                    ret.add(t);
            }
        }
        else
        {
            d = Pathfinding.GetDist2(p, n.t.getPosition());
            if(d <= d2)
                ret.add(n.t);
            if(n.axis == 0)
                d = p.getX() - (double)n.val;
            else
                d = p.getY() - (double)n.val;
            if(d < 0)
            {
                ret.addAll(nearbySub(p, dist, n.childA));
                if(d <= dist)
                    ret.addAll(nearbySub(p, dist, n.childB));
            }
            else
            {
                ret.addAll(nearbySub(p, dist, n.childB));
                if(d <= dist)
                    ret.addAll(nearbySub(p, dist, n.childA));
            }
        }
        return ret;
    }
    
    private node mklvl(Tower[] t, int axis)
    {
        node n = new node();
        if(t.length <= LEAF_TRESHOLD)
        {
            n.leafNodes = new ArrayList<Tower>(t.length);
            n.leafNodes.addAll(Arrays.asList(t));
            return n;
        }
        SortArray(t, axis);
        int midEl = (t.length) / 2;
        n.t= t[midEl];
        n.axis = axis;
        if(axis == 0)
            n.val = t[midEl].x;
        else
            n.val = t[midEl].y;
        Tower[] tA = new Tower[midEl],
                tB = new Tower[t.length - 1 - midEl];
        System.arraycopy(t, 0, tA, 0, midEl);
        System.arraycopy(t, midEl + 1, tB, 0, t.length - 1 - midEl);
        
        n.childA = mklvl(tA, 1 - axis);
        n.childB = mklvl(tB, 1 - axis);
        n.childA.parent = n;
        n.childB.parent = n;
        return n;
    }
    
    public KDTree(Tower[] t)
    {
        if(t != null)
            parent = mklvl(t, 0);
    }
    
}
